<!--$Id: intro.so,v 10.25 2004/09/17 19:51:50 bostic Exp $-->
<!--Copyright (c) 1997,2008 Oracle.  All rights reserved.-->
<!--See the file LICENSE for redistribution information.-->
<html>
<head>
<title>Berkeley DB Reference Guide: What are the available access methods?</title>
<meta name="description" content="Berkeley DB: An embedded database programmatic toolkit.">
<meta name="keywords" content="embedded,database,programmatic,toolkit,btree,hash,hashing,transaction,transactions,locking,logging,access method,access methods,Java,C,C++">
</head>
<body bgcolor=white>
<a name="2"><!--meow--></a>
<table width="100%"><tr valign=top>
<td><b><dl><dt>Berkeley DB Reference Guide:<dd>Access Methods</dl></b></td>
<td align=right><a href="../intro/products.html"><img src="../../images/prev.gif" alt="Prev"></a><a href="../toc.html"><img src="../../images/ref.gif" alt="Ref"></a><a href="../am_conf/select.html"><img src="../../images/next.gif" alt="Next"></a>
</td></tr></table>
<p align=center><b>What are the available access methods?</b></p>
<p>Berkeley DB currently offers four access methods: Btree, Hash, Queue and Recno.</p>
<b>Btree</b>
<p>The Btree access method is an implementation of a sorted, balanced tree
structure.  Searches, insertions, and deletions in the tree all take O(log
base_b N) time, where base_b is the average number of keys per page, and
N is the total number of keys stored.  Often, inserting ordered data into
Btree implementations results in pages that are only half-full.  Berkeley DB
makes ordered (or inverse ordered) insertion the best case, resulting in
nearly full-page space utilization.</p>
<b>Hash</b>
<p>The Hash access method data structure is an implementation of Extended
Linear Hashing, as described in "Linear Hashing: A New Tool for File and
Table Addressing", Witold Litwin, <i>Proceedings of the 6th
International Conference on Very Large Databases (VLDB)</i>, 1980.</p>
<b>Queue</b>
<p>The Queue access method stores fixed-length records with logical record
numbers as keys.  It is designed for fast inserts at the tail and has a
special cursor consume operation that deletes and returns a record from
the head of the queue.  The Queue access method uses record level locking.</p>
<b>Recno</b>
<p>The Recno access method stores both fixed and variable-length records with
logical record numbers as keys, optionally backed by a flat text (byte
stream) file.</p>
<table width="100%"><tr><td><br></td><td align=right><a href="../intro/products.html"><img src="../../images/prev.gif" alt="Prev"></a><a href="../toc.html"><img src="../../images/ref.gif" alt="Ref"></a><a href="../am_conf/select.html"><img src="../../images/next.gif" alt="Next"></a>
</td></tr></table>
<p><font size=1>Copyright (c) 1996,2008 Oracle.  All rights reserved.</font>
</body>
</html>
